package vip.zhenzicheng.algorithm.leetcode.binary_search;

/**
 * <a href="https://leetcode.cn/problems/binary-search/">二分查找 [简单]</a>
 *
 * @author zhenzicheng
 * @date 2022-06-10 11:16
 */
public class BinarySearch_704 {

  // 二分查找 递归
  public static int binarySearch(int[] arr, int L, int R, int key) {
    int mid = (L + R) / 2; // 在[L,R]上折半
    if (L <= R) {
      if (key > arr[mid]) {
        return binarySearch(arr, mid + 1, R, key);
      } else if (key < arr[mid]) {
        return binarySearch(arr, L, mid - 1, key);
      } else {
        return mid;
      }
    }
    return -1;
  }

  // 二分查找 迭代
  public static int binarySearch2(int[] nums, int target) {
    int start = 0, end = nums.length - 1;
    while (start <= end) {
      int mid = (start + end) / 2;
      if (target > nums[mid]) {
        start = mid + 1;
      } else if (target < nums[mid]) {
        end = mid - 1;
      } else {
        return mid;
      }
    }
    return -1;
  }

  public int search(int[] nums, int target) {
    if (nums.length == 1) {
      return nums[0] == target ? 0 : -1;
    }

    // return binarySearch(nums, 0, nums.length - 1, target);
    return binarySearch2(nums, target);
  }
}
